최장 증가 부분 수열

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요
2. 알고리즘
- 2.1. 이진 검색
  - 2.1.1. 알고리즘 구현 (파이썬)
3. 다른 알고리즘 문제와의 관계
4. 이론적 분석
5. 온라인 알고리즘
참조

1. 개요

최장 증가 부분 수열(LIS)은 주어진 수열에서 원소들이 오름차순으로 정렬된 부분 수열 중 가장 긴 수열을 찾는 문제이다. 에르되시-세케레시 정리는 모든 수열이 길이 n+1의 증가 또는 감소하는 부분 수열을 갖는다는 것을 보여준다. 이 문제는 동적 계획법, 이진 검색과 같은 다양한 알고리즘으로 해결될 수 있으며, 시간 복잡도는 O(n log n)이다. LIS는 최장 공통 부분 수열 문제, 순열 그래프, 로빈슨-쉔슈테드 대응과 같은 다른 알고리즘 문제와 관련이 있다. 또한 온라인 알고리즘 환경에서도 연구되었으며, 무작위 순열의 경우 최장 증가 부분 수열의 예상 길이는 대략 2√n이다.

더 읽어볼만한 페이지

동적 계획법 - 배낭 문제
배낭 문제는 주어진 배낭 용량 내에서 물건들의 가치 합을 최대화하는 조합 최적화 문제로, 물건을 쪼갤 수 있는지, 개수 제한이 있는지에 따라 다양한 변형이 있으며, 동적 계획법, 탐욕 알고리즘 등으로 해결하고, NP-완전 문제에 속하며 자원 할당 문제 등에 응용된다.
동적 계획법 - 차원의 저주
차원의 저주는 고차원 공간에서 데이터 분석 및 모델링의 어려움을 나타내는 현상으로, 계산 시간 증가, 수치 오차 발생, 조합 폭발 등의 문제점을 야기한다.
수열 - 코시 열
코시 열은 무한수열에서 항들이 뒤로 갈수록 서로 가까워지는 수열로, 수렴열은 항상 코시 열이지만 그 역은 성립하지 않을 수 있으며, 실수의 완비성 정의 및 무한급수 수렴성 판정에 중요한 역할을 하는 개념이다.
수열 - 실베스터 수열
실베스터 수열은 각 항이 이전 항들의 곱에 1을 더한 값으로 정의되는 정수 수열로서, 재귀적으로 정의되며 이중 지수 함수적으로 증가하고, 이집트 분수 및 탐욕 알고리즘과 관련이 있으며, 역수 합은 1로 수렴한다.
알고리즘 - 텍스트-비디오 모델
텍스트-비디오 모델은 텍스트 입력을 기반으로 비디오를 생성하는 인공지능 모델로서, 다양한 모델들이 개발되고 교육, 홍보, 창작 산업 등 여러 분야에 활용되지만 컴퓨팅 자원 소모, 데이터 부족, 텍스트 해석 오류, 윤리적 문제 등의 한계점을 가진다.
알고리즘 - 마스터 정리
마스터 정리는 분할 정복 알고리즘의 시간 복잡도 분석 도구로서, 점화식을 세 가지 경우로 나누어 재귀 알고리즘의 효율성을 파악하고, 다양한 정렬 및 일반 알고리즘 분석에 활용되지만, 특정 조건에서는 적용이 제한될 수 있습니다.

최장 증가 부분 수열
개요
최장 증가 부분 수열의 예시 (길이 4).
문제 유형	조합 최적화
해결 방법	동적 계획법 인내 정렬
정의
입력	수열
목표	가장 긴 증가 부분 수열 찾기
복잡도
시간 복잡도	O(n log n) (최적)
공간 복잡도	O(n)
관련 개념
관련 항목	최장 공통 부분 수열 최장 감소 부분 수열 인내 정렬
참고 문헌
참고 문헌	"Longest Increasing Subsequences: From Patience Sorting to the Baik–Deift–Johansson Theorem" (Aldous, David; Diaconis, Persi (1999)) "The Surprising Mathematics of Longest Increasing Subsequences" (Romik, Dan (2015)) "Longest increasing and decreasing subsequences" (Schensted, C. (1961))

2. 알고리즘

최장 증가 부분 수열 문제를 해결하기 위한 여러 알고리즘이 존재한다. 그중 대표적인 방법으로는 이진 검색을 활용하여 O(n log n)의 시간 복잡도를 가지는 효율적인 알고리즘이 있다. 이 알고리즘은 입력 수열을 순차적으로 처리하며 각 단계에서 최적의 부분 수열 정보를 갱신하는 방식으로 동작한다.

2. 1. 이진 검색

배열과 이진 검색을 활용하여 최장 증가 부분 수열 문제를

O(n \log n)

시간 복잡도로 해결하는 효율적인 알고리즘이 존재한다. 이 알고리즘은 입력 수열

X

의 원소를

X[0], X[1], \ldots

순서대로 처리하면서, 각 단계까지 발견된 최장 증가 부분 수열에 대한 정보를 유지하고 갱신한다.

알고리즘은 주로 다음 세 가지 정보를 관리한다:

$L$ : 현재까지 발견된 최장 증가 부분 수열의 길이.
$M$ : 배열 $M$ 은 각 길이 $l$ 에 대해, 해당 길이를 가지는 증가 부분 수열을 만들 수 있는 가장 작은 마지막 원소 $X[k]$ 의 인덱스 $k$ 를 저장한다. 즉, $M[l] = k$ 는 $X[k]$ 가 길이 $l$ 인 증가 부분 수열의 마지막 값이면서, 가능한 모든 길이 $l$ 짜리 증가 부분 수열의 마지막 값 중 가장 작은 값임을 의미한다. 중요한 속성으로, $X[M[1]], X[M[2]], \ldots, X[M[L]]$ 값들은 항상 오름차순으로 정렬되어 있어 이진 검색을 효율적으로 사용할 수 있다.
$P$ : 배열 $P$ 는 최종적으로 최장 증가 부분 수열 자체를 복원하기 위해 사용된다. $P[k]$ 는 $X[k]$ 를 마지막 원소로 하는 최장 증가 부분 수열에서 $X[k]$ 바로 앞에 오는 원소의 인덱스를 저장한다.

알고리즘의 핵심 과정은 입력 수열

X

의 각 원소

X[i]

를 순서대로 처리하며,

M

배열에 저장된 값들에 대해 이진 검색을 수행하는 것이다. 이진 검색을 통해

X[i]

가 기존 증가 부분 수열을 확장하거나 대체할 최적의 위치(길이

l

)를 찾는다. 이후

M[l]

과

P[i]

값을 갱신하고, 필요한 경우 최장 길이

L

도 업데이트한다. 모든 원소를 처리한 후,

L

은 최장 증가 부분 수열의 길이가 되며,

P

배열을 역추적하여 실제 수열을 복원할 수 있다.

이 알고리즘은 각 원소

X[i]

에 대해 한 번의 이진 검색(

O(\log n)

시간 소요)을 수행하므로, 전체 시간 복잡도는 O(n log n)이다. Fredman (1975)은 이 알고리즘의 변형을 논의하며 도널드 커누스에게 그 공을 돌렸다. 이 변형은 비교 횟수를 더욱 최적화하여

n \log_2 n - n \log_2 \log_2 n + O(n)

비교를 사용하며, 이는 비교 기반 알고리즘에 대해 최적에 가깝다.^[6]

2. 1. 1. 알고리즘 구현 (파이썬)

다음은 배열과 이진 검색을 사용하여 최장 증가 부분 수열 문제를 ''O''(n log n) 시간 복잡도로 해결하는 알고리즘의 파이썬 유사 코드 구현 예시이다. 이 알고리즘은 주어진 순서열 ''X''의 원소를 순서대로 처리하며, 각 단계에서 최장 증가 부분 수열 정보를 갱신한다.

알고리즘은 다음 변수들을 사용한다:

''L'': 현재까지 발견된 최장 증가 부분 수열의 길이.
''M'': ''M''[''l'']은 길이가 ''l''인 증가 부분 수열을 만들 수 있는 가장 작은 마지막 원소 ''X''[''k'']의 인덱스 ''k''를 저장한다. 즉, ''X''[''M''[''l'']]은 길이가 ''l''인 모든 증가 부분 수열의 마지막 원소 값 중 가장 작은 값이다.
''P'': ''P''[''k'']는 ''X''[''k'']를 마지막 원소로 하는 최장 증가 부분 수열에서 ''X''[''k''] 바로 이전 원소의 인덱스를 저장한다. 이 배열은 최종적으로 최장 증가 부분 수열을 복원하는 데 사용된다.

아래는 알고리즘의 진행 과정을 나타낸 파이썬 유사 코드이다. 배열 인덱스는 0부터 시작한다고 가정한다.

```python

# P: 이전 원소 인덱스 저장 배열 (길이 N)

# M: 각 길이별 최소 마지막 원소 인덱스 저장 배열 (길이 N + 1)

P = [0] * N

M = [0] * (N + 1)

M[0] = -1 # M[0]은 사용되지 않으므로 임의의 값으로 설정

L = 0 # 최장 증가 부분 수열의 길이

for i in range(N): # 입력 배열 X의 각 원소 X[i]에 대해 반복

# 이진 검색: X[M[mid]] >= X[i]를 만족하는 가장 작은 l을 찾는다 (1 <= l <= L).

# 즉, X[i]가 기존의 어떤 증가 부분 수열의 마지막 원소보다 작거나 같으면,

# 그 중 가장 작은 값을 가지는 부분 수열을 찾아 그 자리를 대체할 후보가 된다.

lo = 1

hi = L + 1

while lo < hi:

mid = lo + (hi - lo) // 2 # 중간 인덱스 계산

if X[M[mid]] >= X[i]:

hi = mid # X[i]가 X[M[mid]]보다 작거나 같으면, mid 혹은 그 이전 위치에 삽입 가능

else: # X[M[mid]] < X[i]

lo = mid + 1 # X[i]가 X[M[mid]]보다 크면, mid 이후 위치에 삽입 가능

# 이진 검색 종료 후, lo는 X[i]를 마지막 원소로 하는 증가 부분 수열의 길이를 의미한다.

newL = lo

# P 배열 업데이트: X[i]의 이전 원소는 길이가 newL-1인 증가 부분 수열의 마지막 원소이다.

P[i] = M[newL - 1]

# M 배열 업데이트: 길이가 newL인 증가 부분 수열을 만드는 가장 작은 마지막 원소의 인덱스를 i로 갱신한다.

M[newL] = i

if newL > L:

# X[i]를 통해 더 긴 증가 부분 수열을 만들 수 있다면, 최장 길이 L을 갱신한다.

L = newL

# 최장 증가 부분 수열(LIS) 재구성

# P 배열을 역추적하여 LIS를 찾는다.

S = [0] * L # 결과를 저장할 배열

k = M[L] # 최장 길이 L을 달성한 마지막 원소의 인덱스

for j in range(L - 1, -1, -1): # L-1부터 0까지 역순으로 반복

S[j] = X[k] # 결과 배열에 원소 저장

k = P[k] # P 배열을 따라 이전 원소의 인덱스로 이동

# return S # 최장 증가 부분 수열 반환

```

이 알고리즘은 각 원소 ''X''[''i'']에 대해 한 번의 이진 검색을 수행하므로, 전체 시간 복잡도는 ''O''(n log n)이다. 이 알고리즘의 변형으로, 각 단계에서 상수 시간 검사를 통해 이진 검색 필요 여부를 판단하여 비교 횟수를 최적화하는 방법도 존재한다.^[6]

'''실행 예시'''

다음은 입력 배열 `X = [2, 8, 9, 5, 6, 7, 1]`에 대해 알고리즘이 실행되는 과정을 보여주는 표이다.

X = [2, 8, 9, 5, 6, 7, 1] 실행 과정
변수에 저장된 값	X[i]	newL	P	M	X[M]	L
for i 루프 시작 전			P = []	M = [-1]	X[M] = [N/A]	L = 0
루프 i = 0 종료 시	X[0] = 2	newL = 1	P = [-1]	M = [-1, 0]	X[M] = [N/A, 2]	L = 1
루프 i = 1 종료 시	X[1] = 8	newL = 2	P = [-1, 0]	M = [-1, 0, 1]	X[M] = [N/A, 2, 8]	L = 2
루프 i = 2 종료 시	X[2] = 9	newL = 3	P = [-1, 0, 1]	M = [-1, 0, 1, 2]	X[M] = [N/A, 2, 8, 9]	L = 3
루프 i = 3 종료 시	X[3] = 5	newL = 2	P = [-1, 0, 1, 0]	M = [-1, 0, 3, 2]	X[M] = [N/A, 2, 5, 9]	L = 3
루프 i = 4 종료 시	X[4] = 6	newL = 3	P = [-1, 0, 1, 0, 3]	M = [-1, 0, 3, 4]	X[M] = [N/A, 2, 5, 6]	L = 3
루프 i = 5 종료 시	X[5] = 7	newL = 4	P = [-1, 0, 1, 0, 3, 4]	M = [-1, 0, 3, 4, 5]	X[M] = [N/A, 2, 5, 6, 7]	L = 4
루프 i = 6 종료 시	X[6] = 1	newL = 1	P = [-1, 0, 1, 0, 3, 4, -1]	M = [-1, 6, 3, 4, 5]	X[M] = [N/A, 1, 5, 6, 7]	L = 4
변수에 저장된 값	S				k	X[k]
for j 루프 시작 전	S = [N/A, N/A, N/A, N/A]				k = M[4] = 5	X[5] = 7
루프 j = 3 종료 시	S = [N/A, N/A, N/A, 7]				k = P[5] = 4	X[4] = 6
루프 j = 2 종료 시	S = [N/A, N/A, 6, 7]				k = P[4] = 3	X[3] = 5
루프 j = 1 종료 시	S = [N/A, 5, 6, 7]				k = P[3] = 0	X[0] = 2
루프 j = 0 종료 시	S = [2, 5, 6, 7]				k = P[0] = -1	X[-1] = N/A

최종적으로 반환되는 최장 증가 부분 수열은 `[2, 5, 6, 7]`이다.

3. 다른 알고리즘 문제와의 관계

최장 증가 부분 수열 문제는 최장 공통 부분 수열 문제, 순열 그래프에서의 클리크 및 독립 집합 문제, 그리고 로빈슨-쉔스테드 대응과 같은 다른 여러 알고리즘 문제와 밀접한 관련이 있다.^[3]^[4]^[5]

3. 1. 최장 공통 부분 수열 문제

최장 증가 부분 수열 문제는 최장 공통 부분 수열 문제와 밀접한 관련이 있다. 어떤 수열 S가 주어졌을 때, 이 수열 S와 S를 오름차순으로 정렬한 수열 T 사이의 최장 공통 부분 수열은 원래 수열 S의 최장 증가 부분 수열과 동일하다. 이러한 연관성 때문에, 최장 공통 부분 수열 문제를 해결하는 데 사용되는 이차 시간 동적 계획법 해법을 최장 증가 부분 수열 문제에도 적용할 수 있다.^[3]

3. 2. 순열 그래프

순열 그래프에서 가장 큰 클리크는 해당 그래프를 정의하는 순열의 최장 감소 부분 수열과 같다. 마찬가지로, 순열 그래프의 최대 독립 집합은 최장 비감소 부분 수열과 같다. 따라서 최장 증가 부분 수열 알고리즘은 순열 그래프에서 클리크 문제를 효율적으로 해결하는 데 사용될 수 있다.^[4]

3. 3. 로빈슨-쉔스테드 대응

순열과 영 타블로 사이의 로빈슨-쉔스테드 대응에서, 순열에 해당하는 타블로의 첫 번째 행의 길이는 순열의 최장 증가 부분 수열의 길이와 같고, 첫 번째 열의 길이는 최장 감소 부분 수열의 길이와 같다.^[5]

4. 이론적 분석

최장 증가 부분 수열의 길이에 대한 다양한 이론적 연구가 진행되었다. 대표적으로 에르되시-세케레시 정리는 주어진 길이의 수열에서 특정 길이 이상의 증가 또는 감소 부분 수열이 반드시 존재함을 보여준다. 또한, 무작위 순열에서 최장 증가 부분 수열의 길이는 평균적으로 $2 \sqrt{n}$ 에 가까우며, 그 분포는 트레이시-위덤 분포를 따른다는 것이 바이크-데이프트-요한슨 정리를 통해 알려져 있다. 이러한 이론적 결과들은 최장 증가 부분 수열 문제의 수학적 특성을 이해하는 데 중요한 기초를 제공한다.

4. 1. 에르되시-세케레시 정리

에르되시-세케레시 정리에 따르면, n² + 1개의 서로 다른 정수로 이루어진 모든 수열은 길이 n + 1의 증가하거나 감소하는 부분 수열을 갖는다.^[7]^[8] 각 입력의 순열이 동일하게 나타날 가능성이 있는 입력의 경우, 최장 증가 부분 수열의 예상 길이는 대략 2√n이다.^[9]^[2]

n이 무한대에 가까워질 때, 바이크-데이프트-요한슨 정리는 n개의 항목으로 무작위로 순열된 수열의 최장 증가 부분 수열의 길이가 트레이시-위덤 분포에 가까워지는 분포를 가지며, 이는 가우스 유니타리 앙상블에서 무작위 행렬의 가장 큰 고유값의 분포라고 말한다.^[10]

4. 2. 무작위 순열에서의 최장 증가 부분 수열의 길이

각 입력의 순열이 동일한 확률로 나타나는 무작위 순열의 경우, 최장 증가 부분 수열의 평균적인 길이는 대략

2 \sqrt{n}

이다.^[9]^[2]

더 나아가,

n

이 무한히 커질 때,

n

개의 항목으로 이루어진 무작위 순열에서 최장 증가 부분 수열의 길이는 특정 확률 분포에 가까워진다. 바이크-데이프트-요한슨 정리에 따르면, 이 분포는 트레이시-위덤 분포이며, 이는 가우스 유니타리 앙상블에서 무작위 행렬의 가장 큰 고유값의 분포와 동일하다.^[10]

4. 3. 트레이시-위덤 분포

바이크-데이프트-요한슨 정리는

n

개의 항목을 무작위로 나열한 순열에서 최장 증가 부분 수열의 길이를 다룬다. 이 정리에 따르면,

n

이 무한대에 가까워질수록 최장 증가 부분 수열 길이의 분포는 트레이시-위덤 분포에 수렴한다. 이 분포는 가우스 유니타리 앙상블에서 무작위 행렬의 가장 큰 고유값 분포와 동일하다.^[10]

5. 온라인 알고리즘

최장 증가 부분 수열 문제는 온라인 알고리즘 환경에서도 연구되었다. 이 환경에서는 연속 분포 $F$ 를 따르는 독립 확률 변수들의 수열이나 임의 순열의 원소들이 한 번에 하나씩 순서대로 주어진다. 알고리즘은 다음에 어떤 원소가 올지 모르는 상태에서 각 원소를 부분 수열에 포함할지 여부를 즉시 결정해야 한다.

이러한 온라인 환경에서, 크기 $n$ 인 임의 표본이 입력으로 주어졌을 때, 약 $\sqrt{2 n}$ 의 기대 길이를 가지는 가장 긴 증가 부분 수열을 만들어내는 최적의 선택 방법이 존재한다.^[11] 이 최적의 방법에 따라 선택된 증가 부분 수열의 길이는 약 $\sqrt{2 n} / 3$ 의 분산을 가지며, 그 분포는 정규 분포에 점근적으로 가까워진다.^[12]

이와 유사한 점근적 결과는 푸아송 도착 과정(Poisson arrival process) 환경에서도 성립하며, 더 정확한 경계값들이 제시되었다.^[13] 더 나아가 푸아송 과정 환경에서는 최적 선택 과정에 대한 중심 극한 정리 증명을 통해 이론이 개선되었는데, 이는 적절한 정규화를 통해 예상보다 더 완전한 형태로 나타난다. 이 증명 과정에서는 "정확한" 함수적 극한 정리뿐만 아니라, 관련된 모든 상호 작용 과정을 요약하는 삼차원 과정의 (특이) 공분산 행렬도 함께 제시되었다.^[14]

참조

_[1] 논문 Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem
_[2] 서적 The Surprising Mathematics of Longest Increasing Subsequences
_[3] 논문 A fast algorithm for computing longest common subsequences
_[4] 서적 Algorithmic Graph Theory and Perfect Graphs Academic Press
_[5] 간행물 Longest increasing and decreasing subsequences
_[6] 논문 On computing the length of longest increasing subsequences
_[7] 간행물 A combinatorial problem in geometry http://www.numdam.or[...]
_[8] 간행물 Discrete Probability and Algorithms http://www-stat.whar[...] Springer-Verlag
_[9] 간행물 Asymptotics of the Plancheral measure of the symmetric group and a limiting form for Young tableaux
_[10] 논문 On the distribution of the length of the longest increasing subsequence of random permutations
_[11] 논문 Optimal Sequential Selection of a Monotone Sequence From a Random Sample https://apps.dtic.mi[...]
_[12] 논문 Optimal online selection of a monotone subsequence: a central limit theorem
_[13] 논문 Optimal rules for the sequential selection of monotone subsequences of maximum expected length
_[14] 논문 A central limit theorem for the optimal selection process for monotone subsequences of maximum expected length
_[15] 서적 The surprising mathematics of longest increasing subsequences Cambridge University Press 2015
_[16] 논문 Longest increasing subsequences: from patience sorting to the Baik–Deift–Johansson theorem
_[17] 간행물 Longest increasing and decreasing subsequences

본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com